public class ExMath {
    public static boolean isPrime(int x) {
        if (x == 1) return false;
        if (x == 2 || x == 3) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(x + 1); i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }

    //动态规划求斐波那契数
    //T=O(N)
    public static long fibonacci_dp(int n) {
        //f(0)=f(1)=1
        if (n <= 1) return 1;
        long last = 1, nextToLast = 1, answer = 1;
        for (int i = 2; i <= n; i++) {
            answer = last + nextToLast;
            nextToLast = last;
            last = answer;
        }
        return answer;
    }

    public static long dec2Bi(int x) {
        int remainder = x;
        long ret = 0;
        int level = 0;
        while (remainder != 0) {
            ret += (long) remainder % 2 * Math.pow(10, level++);
            remainder /= 2;
        }
        return ret;
    }

    public static int min(int a, int b, int c) {
        int ret = a;
        if (ret > b) ret = b;
        if (ret > c) ret = c;
        return ret;
    }

    //求两个正整数的最大公因数
    public static int gcd(int a, int b) {
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        int remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }

    //求三个正整数的最大公因数
    public static int gcd(int a, int b, int c) {
        //求多个数的最大公因数：多次辗转相除法
        //先求a,b的最大公因数gcd(a,b),再求gcd(a,b)与c的最大公因数
        int tmp = gcd(a, b);
        return gcd(tmp, c);
    }

    public static long fibonacci(int n) {
        if (n == 1 || n == 2) return 1;
        else return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static long fact(int n) {
        if (n < 0) return 0;
        if (n == 0 || n == 1) return 1;
        else return n * fact(n - 1);
    }
}
